let arr = [1,6,4,3,2]

// 冒泡排序 o(n^2)
// 遍历，比较相邻的两个值，每一回都能把最大的数冒泡的最后面
//
/**
 * 比如： 1和6比，不用换
 *      6 和 4 比，需要把 4，6 交换位置   1，4，6，3，2
 *      6 和 3 比，需要把 6,3 交换位置  1,4,3,6,2
 *      6 和 2 比， 需要把 6，2 交换位置 于是 1,4,3,2,6
 *      只一个 o(n)操作，确定了 6 是最大的元素，把6放到最后，
 *      所以，每次冒泡都会有一个排序完成，所以n个元素，就需要 n 次
 *      如果一次循环中没有交换数据，说明数组已经排序好了，就退出循环
 *
 *      冒泡排序是稳定排序算法吗？
 *      因为只有左值比右值大的时候才交换，所以相等的元素顺序并没有变化。他是稳定的排序算法
 *
 * @param arr
 */
function bubbleSort(arr) {
    if (arr.length < 2) return // 只有一个数，就不用排序
    for (let i = 0; i < arr.length - 1; i++) { // i 是用来计数的，因为每轮循环都至少有一个数排序完成
        let flag = false
        for (let j = 0;j<arr.length - i -1;j++){ // arr.length - i 是因为每次循环都会少一个需要排序的数
            if (arr[j] > arr[j+1]){
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j + 1] = temp
                flag = true
            }
        }
        if (!flag){
            break
        }
    }
    return arr
}

console.log(bubbleSort(arr))

// TODO: 插入排序
/**
 * 插入排序分为已排序区和未排序区，
 * 初始情况，已排序区就是数组第一个元素
 * 然后从未排序区间依次遍历   和已排序区间最后一个比较，因为已排序区间最后一个元素是最大的，如果比他还大，直接放在他后面就行了，否则，就把已排序区间的大数字往右移动
 *
 * @param arr
 */
function insertSorted(arr) {
    if (arr.length < 2) return arr // 如果只有一个数，直接返回就行
    for (let i = 1;i<arr.length;i++){ // i 就是未排序区间的数的下标，要遍历完呢
        let willSwap = arr[i]
        for (let j = i - 1;j>=0;j--){ // j 是已排序区间，已排序区间最大的数字就是i左边那位，如果比他还小，i左边那位就需要让位子啦
            if (willSwap >= arr[j]){
                arr[j+1] = willSwap // 要交换的数字，比前一个数字大，就把这个数字放这里把
                break
            }else { // 不然的话，需要前面的让位子
                arr[j+1] = arr[j] // arr[j] 移到 arr[j+1] 的位置，继续
                arr[j] = willSwap // 必须交换一下位置，不然有可能从这里  for 循环就结束了哇
            }
        }
    }
    return arr
}

console.log(insertSorted(arr))

// 选择排序
/**
 * 选择排序和插入排序类似，也分为已排序区间和未排序区间
 * 不过每次从未排序区间选择一个最小的数放在已排序区间的最尾，所以已排序区默认是无值的，他留着放最小的值呢。
 * 每次交换遍历到的值和最小的值
 * @param arr
 */
function selectedSorted(arr) {
    if (arr.length < 2) return arr
    for (let i=0;i<arr.length - 1;i++){ // arr.length - 1 就行，因为剩下最后一个值肯定是最大的，不用比较了
        let minPos = i
        for (let j = i;j<arr.length;j++){ // 得在所有中找最小的值呢
            if (arr[j] < arr[minPos]){ // 找到了? 遍历完才知道呢
                minPos = j
            }
        }
        // 到这里遍历一遍了，找到最小值了，准备交换啦
        let temp = arr[i]
        arr[i] = arr[minPos]
        arr[minPos] = temp
    }
    return arr
}

console.log(selectedSorted(arr))

// 希尔排序
/**
 * 采用间距逐渐缩小的方法，比较两个间距，插入排序。
 */


// 归并排序
/**
 * 先将大数组拆成一个一个的小数组，单独比较，最后合并
 * 需要两个函数，一个用来不断分割数组，一个用来合并
 * 他是一个稳定的排序算法
 * 但是他不是原位排序的
 */
function mergeSort(arr) { // 这个函数负责拆分
    // 拆分，啥时候就拆分完了呢？直至最后一个没法往下分了
    let {length} = arr
    if (length < 2){
        return arr
    }
    let mid = Math.ceil(length/2)
    let left = mergeSort(arr.slice(0,mid)) // 左边继续拆，直到剩一个元素为止
    let right = mergeSort(arr.slice(mid)) // 右边继续拆，直到剩一个元素为止
    // 第一次执行到这里说明 已经拆完啦，开始合并。。因为是栈结构嘛，怎么拆的，就怎么合
    // 所以归并排序是一个先分解，后排序的过程
    return merge(left, right)
}
function merge(left,right){ // 这个函数负责合并两个数组，依次比较两边的
    let temp = []
    let i = 0,j = 0
    while (left.length - i > 0 && right.length - j > 0){
        if (left[i] <= right[j]){
            temp.push(left[i])
            i++
        }else {
            temp.push(right[j])
            j++
        }
    }
    // 返回的时候，要把只剩一个元素的数组加上
    return temp.concat(i<left.length?left.slice(i):right.slice(j))
}

console.log("--",mergeSort([1,32,43,22,4,1,3,54]))

// 快速排序
function quickSort(arr){ // 主函数
    if (arr.length < 2){
        return arr
    }
    return quick(arr, 0 , arr.length - 1)
}

function quick(arr, left, right){
    let index = partion(arr, left, right) // 获取分割数组的index，这个index 前边的数都比后面的数大
    if(left < index - 1){ // index 比这次的 left 还要大，说明还能继续往下分
        quick(arr, left, index - 1) // 这次分的数组就是 [left, index]  arr[index] 肯定比前面的都大，他们也不用排了
    }
    if (index < right){ // index 比右边的数还小，说明大数组还能分 [index, right]
        quick(arr, index, right)
    }
    return arr
}

function partion(arr, left ,right) {
    let piv = arr[Math.floor((left + right)/2)]
    let i = left
    let j = right
    while (i <= j) {
        while (arr[i] < piv) // 两个判断，一个都不能划等号，不然 i一直加，j一直减，永远没完没了，死循环了
        { // 从头开始，一直比 piv小，就一直不比较
            i++
        }
        while (arr[j] > piv) { // 从头开始，一直比 piv 大，或者等于，都不管，不需要交换
            j--
        }
        if (i <= j) { // i<j 的时候才可以交换位置
            [arr[i],arr[j]] = [arr[j],arr[i]]
            i++
            j--
        }
    }
    return i // 返回最小的那边最大的数，即划分大小的依据
}

console.log("快排",quickSort([1,32,43,22,4,1,3,54]))